package HOT;

import java.util.Stack;

/**
 * Author  zxy
 * Date  2023/7/1 13:43
 */

/*
* 739.每日温度
* https://leetcode.cn/problems/daily-temperatures/
* 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，
* 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，
* 请在该位置用 0 来代替。
* */

public class DailyTemperatures_739 {
    public int[] dailyTemperatures(int[] temperatures) {

        int len = temperatures.length;
        int[] ret = new int[len];

        // for (int i = 0; i < len; i++) {
        //     for (int j = i + 1; j < len; j++) {
        //         if (temperatures[i] < temperatures[j]) {
        //             ret[i] = j - i;
        //             break;
        //         }
        //     }
        // }

        // 单调栈
        Stack<Integer> stack = new Stack<>();
        int index = -1;
        int current = 0;
        for (int i : temperatures) {
            index++;

            while (!stack.isEmpty() && temperatures[stack.peek()] < i) {
                current = stack.pop();
                ret[current] = index - current;
            }

            stack.push(index);
        }

        return ret;

    }
}